package data.automaton;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

public class RandomQuery {

	public static String folder = "/home/quyet/test/data1000";
	public static int maxNeighbor = 4;
	public static int maxState = 6;
	public static String startState = "503";
	public static String terminalState = "10406";
	public static boolean isRandomState = false;
	public static int maxID = 1000;

	public static ArrayList<NodeState> LoadInput(String startNode,
			String terminalNode) throws IOException {
		{
			FileReader fr = new FileReader(new File(folder + "/labels.txt"));
			BufferedReader br = new BufferedReader(fr);

			String strLine;
			ArrayList<NodeState> V = new ArrayList<NodeState>();

			V.add(new NodeState(startNode));

			while ((strLine = br.readLine()) != null) {
				V.add(new NodeState(strLine));
			}

			br.close();

			V.add(new NodeState(terminalNode));

			return V;
		}
	}

	public static ArrayList<NodeState> GeneratorGraph(ArrayList<NodeState> listV) {

		ArrayList<NodeState> listN = listV;
		int n = listN.size();

		boolean isExistTerminal = false;

		Random rd = new Random();

		// remove some node to get enough number of state
		while (n != maxState) {
			int select = rd.nextInt(n);
			if (select != 0 && select != n - 1) {
				listN.remove(select);
				n = n - 1;
			}
		}

		for (NodeState vi : listN) {
			if (!vi.equals(listN.get(n - 1))) {

				int countNeighbors = rd.nextInt(maxNeighbor + 1);

				if (countNeighbors == 0)
					countNeighbors += 1;

				ArrayList<Integer> listIds = new ArrayList<Integer>();
				int count = 0;
				while (count != countNeighbors) {
					int id = rd.nextInt(n);

					if (!listIds.contains((Integer)id)) {
						if (id != 0) { // not connect to start
							NodeState tmp = listN.get(id);
							vi.neighbors.add(tmp.name);
							listIds.add(id);
							count += 1;

							if (id == n - 1)
								isExistTerminal = true;
						}
					}
				}
			}
		}

		if (!isExistTerminal) {
			int id = rd.nextInt(n);
			listN.get(id).neighbors.add(listN.get(n - 1).name);
		}

		return listN;

	}

	public static int getIndexOfNodeState(ArrayList<NodeState> listN,
			String name) {
		int id = -1;
		for (NodeState n : listN) {
			id += 1;
			if (n.name.equals(name))
				return id;
		}
		return id;
	}

	// A BFS based function to check whether s can reach t
	public static boolean isReachable(ArrayList<NodeState> listN, NodeState s,
			NodeState t) {

		for (NodeState n : listN)
			n.visit = false;

		if (s.equals(t))
			return true;

		// Create a queue for BFS
		Queue<NodeState> queue = new LinkedList<NodeState>();
		s.visit = true;
		queue.add(s);

		while (!queue.isEmpty()) {
			NodeState v = queue.poll();

			for (String e : v.neighbors) {
				// If this neighbor is the target vertex, then return true
				if (e.equals(t.name))
					return true;
				// Else, continue to do BFS
				int id = getIndexOfNodeState(listN, e);
				if (listN.get(id).visit == false) {
					queue.add(listN.get(id));
					listN.get(id).visit = true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) throws IOException {

		if (isRandomState) {
			Random rd = new Random();
			int start = rd.nextInt(maxID);
			if (start == 0)
				start = 1;
			int terminal = rd.nextInt(maxID);
			while (terminal == start) {
				terminal = rd.nextInt(maxID);
				if (terminal == 0)
					terminal = 1;
			}
			
			startState = start+"";
			terminalState = terminal+"";
		}
		
		ArrayList<NodeState> listV = LoadInput(startState, terminalState);

		boolean ok = false;
		while (!ok) {
			ArrayList<NodeState> listN = GeneratorGraph(listV);
			NodeState s = listN.get(0);
			NodeState t = listN.get(listN.size() - 1);

			if (isReachable(listN, s, t)) {

				ArrayList<NodeState> tmps = new ArrayList<NodeState>();
				for (NodeState n : listN) {
					if (!isReachable(listN, s, n) || !isReachable(listN, n, t))
						tmps.add(n);
				}

				for (NodeState n : listN) {
					ArrayList<String> nbs = new ArrayList<String>();
					for (NodeState rm : tmps) {
						if (n.neighbors.contains(rm.name)) {
							int id = n.neighbors.indexOf(rm.name);
							nbs.add(n.neighbors.get(id));
						}
					}
					n.neighbors.removeAll(nbs);
				}

				listN.removeAll(tmps);

				ok = true;

				FileWriter fEdge = new FileWriter(folder + "/graphquery.txt");
				BufferedWriter bwEdge = new BufferedWriter(fEdge);

				for (NodeState node : listN) {
					System.out.print(node.name);
					bwEdge.write(node.name);
					String neighbors = "";
					for (String nb : node.neighbors) {
						neighbors += "\t" + nb;						
					}
					System.out.print(neighbors+"\n");
					bwEdge.write(neighbors);
					bwEdge.newLine();
				}
				bwEdge.close();

				System.out.print("\nFinished");

			}
		}

	}

}